public class Test {
    /*
    将有序数组转换为二叉搜索树
    class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    TreeNode dfs(int[] nums, int left, int right) {
        if (left > right)
            return null;

        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, left, mid  - 1);
        root.right = dfs(nums, mid + 1, right);

        return root;
    }
}

    有序链表转换二叉搜索树
    class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        // 空
        if (head == null)
            return null;
        // 一个节点
        if (head.next == null)
            return new TreeNode(head.val);
        // 拿到中间节点
        ListNode mid = getMid(head);
        // 作为根节点
        TreeNode root = new TreeNode(mid.val);
        // 遍历左 从head开始
        root.left = sortedListToBST(head);
        // 遍历右 从 mid.next开始
        root.right = sortedListToBST(mid.next);
        return root;
    }

    public ListNode getMid(ListNode head) {
        // 记录slow前的一位 好隔开
        ListNode pre = null;
        ListNode slow = head, fast = head;
        // 快慢指针
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 断开连接
        if (pre != null)
            pre.next = null;
        return slow;
    }
}
    将二叉搜索树变平衡
    class Solution {
    //
    List<Integer> nums = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        // 中序遍历 让结果加入nums中
        inOrder(root);
        TreeNode head = process(nums, 0, nums.size() - 1);
        return head;
    }

    TreeNode process(List<Integer> nums, int left, int right) {
        if (left > right)
            return null;

        int mid = (left + right) / 2;
        // 创建头节点
        TreeNode root = new TreeNode(nums.get(mid));
        //遍历左边 left mid - 1
        root.left = process(nums, left, mid - 1);
        // 遍历右边 mid+1 rgiht
        root.right = process(nums, mid + 1, right);
        return root;

    }

    void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        nums.add(root.val);
        inOrder(root.right);
    }
}
    前 K 个高频元素
    class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 记录次数
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int x : nums) {
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }
        // 创建小根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> hash.get(o1) - hash.get(o2));
        for (Integer key : hash.keySet()) {
            int value = hash.get(key);
            // 不足 放
            if (pq.size() < k) {
                pq.offer(key);
            } else {
                // 比较堆顶
                int top = pq.peek();// 堆顶 key
                if (value > hash.get(top)) {
                    pq.poll();
                    pq.offer(key);
                }
            }
        }

        // 返回最终结果
        int[] ret = new int[k];
        int index = 0;
        for (int x : pq) {
            ret[index++] = x;
        }

        return ret;
    }
}
    存在重复元素 II
    class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //第一个int 记录 nums[i] 第二个int 记录 下标位置
        HashMap<Integer,Integer> hash = new HashMap<>();
        for(int i = 0 ; i < nums.length; i++) {
            //看看是否存在
            if(hash.containsKey(nums[i])) {
                //取出下标与此时下标比较
                if(Math.abs(hash.get(nums[i]) - i) <= k ) {
                    return true;
                }
            }
            hash.put(nums[i],i);
        }
        //没找到
        return false;
    }
}

    缺失的第一个正数
    class Solution {
    public int firstMissingPositive(int[] nums) {
        // 原地哈希算法 nums[i]- 1= i
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // swap
                //注意  先交换nums[nums[i] - 1]的位置 不然会改变nums[i]的值
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
        }
        // 遍历
        for (int i = 0; i < n; i++) {
            if (i + 1 != nums[i])
                return i + 1;
        }
        return n + 1;
    }
}
     */
}
